First, we read the coordinates and initialize the data structures for Prim's algorithm.
Guidance for Step 1
- Read `N`: Get the number of planets.
- Read Coordinates: Loop `N` times and store the `(x, y)` tuples in a list called `planets`.
- Initialize `key`: A list of size `N`. `key[i]` will store the *minimum cost* to connect planet `i` to the MST. Initialize all to `float('inf')`.
- Initialize `parent`: A list of size `N`. `parent[i]` will store the node that connects `i` to the MST.
- Initialize `in_mst`: A boolean list of size `N`. `in_mst[i]` is `True` if planet `i` is already in the MST. Initialize all to `False`.
- Start at Planet 0: Set `key[0]` to `0.0` (it costs 0 to add the first node) and `parent[0]` to `-1` (it has no parent).
import math
def get_distance(p1_coords, p2_coords):
x1, y1 = p1_coords
x2, y2 = p2_coords
return ((x1 - x2)**2 + (y1 - y2)**2)**0.5
# --- 1. Read Input ---
N = int(input())
planets = []
for _ in range(N):
x, y = map(int, input().split())
planets.append( ____ )
# --- 2. Initialize Prim's Data Structures ---
# key[i] = Min cost to connect planet i to the MST
key = [float('inf')] * N
# parent[i] = The planet that planet i connects to
parent = [None] * N
# in_mst[i] = True if planet i is already in the MST
in_mst = [ ____ ] * N
# --- Start the algorithm from Planet 0 ---
# The cost to connect the start node to itself is 0
key[0] = ____
# The start node is the root, no parent
parent[0] = -1
Copied!